Scala a functional programming approach 2: Data Types

Abstract

This document is a efford to introduce the strengths and benefits of functional programming in scala.

We do not claim intellectual property of all the material presented. We specifically refer to the original resources whenever is needed.

The presentation path of the concepts is still under consideration and may be changed in future reviews.

Outline

This notebooks covers:

Parametric polymorphism
ADTs
Pattern matching
Basic immutable collections

Parametric Polymorphism

Scala supports the concept of parametric polymorphism. This is different from object oriented polymorphism.

Let's see an example of monomophic function and how we can convert it to polymorphic:



In [ ]:

    
// Monomorphic function 
// Find the first element of an array that matches the key
def findIndex(key: String, ss: Array[String]): Int =  {

  //Nested function executes a reccursion
  def loop(n: Int): Int = 
    if (n >= ss.length) -1 
    else if (ss(n) == key) n
    else loop(n+1)
  
  //Start the loop
  loop(0)
}

findIndex("c",Array("a", "b", "c", "c")) // "c" exists twice
findIndex("d",Array("a", "b", "c", "c")) // "d" does not exists

We can make the function polymorphic so it can be more general. That is it can find elements of Array of any type A not just Array[String].



In [ ]:

    
def findIndex[A](p: A => Boolean, ss: Array[A]): Int =  {

  //Nested function executes a reccursion
  def loop(n: Int): Int = 
    if (n >= ss.length) -1 
    else if (p(ss(n))) n
    else loop(n+1)
  
  //Start the loop
  loop(0)
}

findIndex((k: String) => k == "b", Array("a", "b", "c", "c")) // works for string arrays 

findIndex((k: Int) => k == 100 , Array(1, 200, 100, 30)) // works for integer arrays

findIndex((k: (String, Int)) => k == ("foo", 1), Array(("bar",4),("foo",1))) // works for product types

Some more examples of parametric polymorphism.



In [ ]:

    
// Parametric polymorphism

// The trivial generic function id.
def id[T](x: T): T = x

id(1)
id("2")
id(List(1,2,3))

// The higher order function compose

def compose[A,B,C] (g: B => C, f: A => B): A => C = (a: A) => g(f(a))

def andThen[A,B,C] (g: A => B, f: B => C): A => C = (a: A) => f(g(a))

def inc(x: Int): Int = x + 1
def double(x: Int): Int = x * 2

compose(inc,double)(1)
compose(double,inc)(1)
compose(double,double)(1)

compose(double,inc)(2) == andThen(inc,double)(2)

Take away

We are using parametric polymorphism to implement general behaviours that apply to families of types. This programming mechanism promotes more general abstractions and code reusability.

Algebraic Data Types (ADTs)

In the previous workshops we talked about descriptions of programs and interpreters of descriptions in order to deal with side effects.

The descriptions in a functional languages are implemented through data types. These data types are forming algebras (under some theoretical conditions) so they are often called Algebraic Data Types (ADTs).

Note: In the workshops that follow we will not concern ourselves with the mathematical point of view of the data types, but we will make use of their properties in an effort to give you some insight of their nature.

Scala Option

We will begin our study with the standard library Option type.

Option is generic type that describes the side effect of a value or absence of a value



In [ ]:

    
def greeting(): Option[String] = Some("Hello!")
def absentGreeting(): Option[String] = None

Option is a parametric data type.

Option has smart costructors which can be viewed as factories of data values.



In [ ]:

    
Option(1)
Option(null) // = None
Option("foo")
Option("")

Option has an get method that extracts the value



In [ ]:

    
Option(1).get
// Option(null).get // This throws get is an UNSAFE OPERATION

Option has many usefull operations such as:



In [ ]:

    
Option("foo").filter(value => value == "foo" )
Option("foo").filter(value => value.length == 4)

Option("foo").exists( value => value == "foo")

// foreach extracts the value of the option and executes a side effect.
Option(3.14).foreach { x => print(x) } 

//DOES NOT EXECUTE (None is absent value so nothing to print)
None.foreach { x => print(x)}

So take a look at the documentation

An example from the past



In [ ]:

    
case class Player(name: String, score: Int)

//A method that finds players in a repository
def fetchPlayerByName(name: String): Option[Player] = { //This repository has two players
  if(name == "fpas") 
    Some(Player("fpas", 10))
  else if (name == "gsmyrn")
    Some(Player("gsmyrn", 5))
  else
    None
}

fetchPlayerByName("fpas")
fetchPlayerByName("gsmyrn")
fetchPlayerByName("gpapag")

Option has a map method



In [ ]:

    
val p1 = fetchPlayerByName("fpas")
  .map( p => p.copy(name = p.name.toUpperCase) )    //capitalize name
  .map( p => p.copy(score = p.score -1 ) )          //Decrease the score by one
  
  
fetchPlayerByName("non Existing player")
  .map( p => p.copy(name = p.name.toUpperCase) )    //capitalize name
  .map( p => p.copy(score = p.score -1 ) )          //Decrease the score by one
    
    
//Same example refactored
def capitalize(p: Player): Player = p.copy(name = p.name.toUpperCase)

def decreaseScore(p: Player): Player = p.copy(score =(p.score - 1) )

val p11 = fetchPlayerByName("fpas")
  .map( p => capitalize(p) )               //capitalize name
  .map( p => decreaseScore(p) )            //Decrease the score by one

p1 == p11
p11.foreach( p => print(p))  //Just printing

Map for option has a signature

def map[A,B](option: Option[A], f: A => B): Option[B]

Map method accepts an option and transforms its internals without altering the structure of the type.

Study case: Recreating a (minimal) Option ATD

Let's recreate Option type as an exersice.

This is idiomatic scala so take a deep breath and relax !



In [ ]:

    
sealed trait Opt[+A]
case object None extends Opt[Nothing]
case class Some[A](value: A) extends Opt[A]

object Opt {
  //Smart constructor
  def apply[A](value: A): Opt[A] = if (value == null) None else Some(value) 
}

// Now we can write
Opt(1)
Opt(null)
Some(1)
Some(1).value 

// Opt(1).value  //Does not compile
// None.value //Does not compile

We have defined a new data type. We can create values of it. But how can we use it ?

Let's talk a little bit about pattern matching an extremely usefull construct in functional programming.

Pattern matching with `Opt`

Pattern matching is the way of scala to inspect the structure of hierarchical types such as Opt.

In some way substitutes the instanceOf of java BUT IT IS NOT THE SAME.



In [ ]:

    
// An example of opt
val maybeInt = Opt(1)
 
//Pattern matching
maybeInt match {
  case Some(a) => println("The internal value of option is " + a)
  case None => println("Option is empty")
}



In [ ]:

    
//Let's make it a generic function 
def inspect[A](opt: Opt[A]): Unit = opt match {
  case Some(a) => println("The internal value of option is " + a)
  case None => println("Option is empty")
}

inspect(Opt(1))
inspect(Opt(null))
inspect(Opt("works with strings"))
inspect(Opt(List(1,2,3)))

Extending Opt to support isEmpty using pattern matching.



In [ ]:

    
sealed trait Opt[+A]
case object None extends Opt[Nothing]
case class Some[+A](value: A) extends Opt[A]


object Opt {
  //Smart constructor
  def apply[A](value: A): Opt[A] = if (value == null) None else Some(value) 
  
  def isEmpty[A](value: Opt[A]): Boolean = value match {
    case Some(a) => false   
    case _ => true     //case _ means everything else 
  }
}

// Now we can write
Opt.isEmpty(Opt(1))
Opt.isEmpty(Opt(null))
Opt.isEmpty(Some("foo"))

//Or like this  (IGNORE locally its a scala-notebook thingy)
locally {

  import Opt._
  
  isEmpty(Opt(1))
  isEmpty(Opt(null))
  isEmpty(Some("foo"))
  isEmpty(Opt(List("this", "is", "a", "list", "of", "strings")))
}

Exercise 1: Implement function map , which changing the internal type of an option but preserves its structure.



In [ ]:

    
sealed trait Opt[+A]
case object None extends Opt[Nothing]
case class Some[+A](value: A) extends Opt[A]


object Opt {
  //Smart constructor
  def apply[A](value: A): Opt[A] = if (value == null) None else Some(value) 
  
  def isEmpty[A](value: Opt[A]): Boolean = value match {
    case Some(a) => true   
    case _ => false//case _ means everything else 
  }
  
  
  def map[A,B](opt: Opt[A], f: A => B): Opt[B] =  ???
}

locally {
  import Opt._

//   map(Opt(null), (x: Int) => x + 1)
  map(None, (x: Int) => x + 1)
  map(Opt(1), (x: Int) => x + 1) // Test with integers
  map(Opt("fotis"), (x: String) => x.toUpperCase) // Test with strings

  case class Player(name: String, score: Int) // Test with product
  map(Opt(Player("fpas",1)), (p: Player) => p.copy(score = p.score + 1))
}

Exercise 2: Implement

filter which keeps the element of an option if a given predicate holds,

exists which tests if a given predicate holds for the option,

foreach which executes a side effect using the value of an option (if any)

Hint: For filter and exists use a case clause with a predicate if expression. ( case ... if ... => ... )



In [ ]:

    
sealed trait Opt[+A]
case object None extends Opt[Nothing]
case class Some[+A](value: A) extends Opt[A]


object Opt {
  //Smart constructor
  def apply[A](value: A): Opt[A] = if (value == null) None else Some(value) 
  
  def isEmpty[A](value: Opt[A]): Boolean = value match {
    case Some(a) => true   
    case _ => false  //case _ means everything else 
  }
  
  def filter[A](opt: Opt[A], p: A => Boolean): Opt[A] = ???

  def exists[A](opt: Opt[A], p: A => Boolean): Boolean =  ???

  def foreach[A, B](opt: Opt[A], f: A => Unit ): Unit = ???

}

locally {
  import Opt._

  filter(Opt(1), (v: Int) => v == 1)
  filter(Opt(1), (v: Int) => v < 0 )
  
  exists(Opt("Fotis"), (v: String) => v == "George")
  exists(Opt("Fotis"), (v: String) => v == "Fotis")
  
  foreach(Opt("Fotis"), println _ )
  foreach(None, println _ ) // Should not execute
}

Scala Immutable List

Scala predef (standard) library provides more types for all types of side effects. Let's consider the case of a List.

List is a generic type that describes the side effect of iteration (a.k.a having meny repeatable ordered elements of some type).



In [ ]:

    
// Immutable List data type
import scala.collection.immutable.List


// Constructing lists
val empty = List()
val numbers = List(1,2,3)
val moreNumbers: List[Int] = 4 :: 5 :: Nil

// Operations
val head = numbers.head
val tail = numbers.tail
val init = numbers.init
val last = numbers.last
val reverse = numbers.reverse


val filtered = numbers.filter(x =>  x < 3)
val existsNumberOne = numbers.exists(x => x == 1)
val mappedList = numbers.map( x => x + 1 )

// Append
numbers ++ moreNumbers

// Prepend element
0 :: numbers // = numbers.::(0)
0 +: numbers

// Append element
moreNumbers :+ 6

// More operations
try { empty.head } catch {case ex => ex} //Note try is an expression!!!

// Also foreach
numbers.foreach(print _)

Study case: Recreating a (minimal) immutable list type

Let's again try to re implement some of the lists functionality.



In [ ]:

    
// Recreating immutable list
sealed trait Lst[+A]
case object Nil extends Lst[Nothing]
case class Cons[+A](head: A, tail: Lst[A]) extends Lst[A]


val empty: Lst[Int] = Nil
val numbers: Lst[Int] = Cons(1, Cons(2, Cons(3, Nil)))


object Lst {

  def apply[A](ss: A*): Lst[A] =      
      if(ss.isEmpty) Nil
      else Cons(ss.head, apply(ss.tail: _*))
}

Lst(1,2,3) //Now we can write

Before we continue note that List is has a recursive type declaration, that is the Cons[A] type constractor refers to Lst[A] recursively.

Also note the numbers instance is a value of Cons(1,Cons(2,Cons(3,Nil)))

That representation of the data structure represents a Linked List

Each node (head) has a payload A and refers (points) to the next node that contains the rest (tail) of the list.

Pattern matching

Let's review pattern matching on lists.



In [ ]:

    
def funnyMatch(l: Lst[String]): String =  l match {
  case (Cons(x, Cons("2", Cons(y, _)))) => x + y
  case Nil => "Nil"
  case Cons("1", _) => "Starting with 1"
  case _ => sys.error("Oops!!!")
}

funnyMatch(Lst())

funnyMatch(Lst("test ", "2", "foo"))

funnyMatch(Lst("1", "2"))

// funnyMatch(Lst("2", "3")) throws Opps!

// funnyMatch(Lst(1,2)) type mismatch

Implementing list operations

Let's continue by implementing head which returns the first element of the list.



In [ ]:

    
sealed trait Lst[+A]
case object Nil extends Lst[Nothing]
case class Cons[+A](head: A, tail: Lst[A]) extends Lst[A]

object Lst {

    def apply[A](ss: A*): Lst[A] =      
      if(ss.isEmpty) Nil
      else Cons(ss.head, apply(ss.tail: _*))
      
    def head[A](l: Lst[A]): A = l match {
       case Nil => sys.error("Invoking head on empty list.")
       case Cons(a,_) => a
    }
}

val list = Lst("1","2","3") 
val emptyList = Lst[String]() // Nil

Lst.head(list)
try { Lst.head(emptyList) } catch { case a: Throwable => a }

Exercise 3:

Implement tail, which returns the tail of non empty list.

Implement setHead, which replaces the head of the list.

Implement drop, which drops the first n elements of the list.



In [ ]:

    
sealed trait Lst[+A]
case object Nil extends Lst[Nothing]
case class Cons[+A](head: A, tail: Lst[A]) extends Lst[A]

object Lst {

    def apply[A](ss: A*): Lst[A] =      
      if(ss.isEmpty) Nil
      else Cons(ss.head, apply(ss.tail: _*))
      
    def head[A](l: Lst[A]): A = l match {
       case Nil => sys.error("Invoking head on empty list.")
       case Cons(a,_) => a
    }
    
     def tail[A](l:Lst[A]): Lst[A] = ???  
    
     def setHead[A](l: Lst[A], head: A): Lst[A] = ???
    
     def drop[A](l: Lst[A], n: Int): Lst[A] = ???

}

Exercise 4: Implement init which returns the first elements of a list without the last one.

Note: Do you see something disturbing with your implementation?



In [ ]:

    
sealed trait Lst[+A]
case object Nil extends Lst[Nothing]
case class Cons[+A](head: A, tail: Lst[A]) extends Lst[A]

object Lst {

    def apply[A](ss: A*): Lst[A] =      
      if(ss.isEmpty) Nil
      else Cons(ss.head, apply(ss.tail: _*))
      
    def head[A](l: Lst[A]): A = l match {
       case Nil => sys.error("Invoking head on empty list.")
       case Cons(a,_) => a
    }
    
    
    def init[A](l: Lst[A]): Lst[A] = ???
}

val list = Lst("1","2","3") 
val singleList = Lst("10")
val emptyList = Lst[String]() // Nil

Lst.init(list)
Lst.init(singleList)
try { Lst.init(emptyList) } catch { case x => x }

Using our list for aggregations

Before we continue let's try and use our list so far by producing some aggregate values using our list.



In [ ]:

    
//Find the sum of the list elements
def sum(l: Lst[Int]): Int = l match {
  case Nil => 0 
  case Cons(h,t) => h + sum(t)
}

sum(Lst(1,2,3,4))

//Find the product of the list elements
def product(l: Lst[Int]): Int = l match {
  case Nil => 1
  case Cons(h,t) => h * sum(t)
} 

product(Lst(1,2,3,4))

Do you see the code duplication?

How can we make that more abstract ?

Introducing folds



In [ ]:

    
sealed trait Lst[+A]
case object Nil extends Lst[Nothing]
case class Cons[+A](head: A, tail: Lst[A]) extends Lst[A]

object Lst {

    def apply[A](ss: A*): Lst[A] =      
      if(ss.isEmpty) Nil
      else Cons(ss.head, apply(ss.tail: _*))
      
    def head[A](l: Lst[A]): A = l match {
       case Nil => sys.error("Invoking head on empty list.")
       case Cons(a,_) => a
    }
    
    
    // Collapses the list to one value using a initial element and a binary operation. 
    // This is done from rigth to left (from the last element to the first)
    def foldRight[A,B](l: Lst[A], z: B)(f: (A,B) => B): B = l match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs,z)(f))
    }
    
    // This is the tail recursive version of the operation above ( it is not always the same why?)
    // Collapses the list to one value using a initial element and a binary operation. 
    // This is done from rigth to left (from the last element to the first)
    @annotation.tailrec
    def foldLeft[A,B](l: Lst[A], z: B)(f: (B, A) => B): B = l match {
      case Nil => z
      case Cons(h,t) => foldLeft(t, f(z,h))(f)
    }
}


//Reimplement sum and product using foldRight
def sum(l: Lst[Int]): Int = Lst.foldRight(l, 0)((x,y) =>  x + y)

sum(Lst(1,2,3,4))

//Find the product of the list elements
def product(l: Lst[Int]): Int = Lst.foldRight(l, 1)(_ * _)

product(Lst(1,2,3,4))

//Reimplement sum and product using foldLeft
def sum1(l: Lst[Int]): Int = Lst.foldLeft(l, 0)((x,y) =>  x + y)

sum1(Lst(1,2,3,4))

//Find the product of the list elements
def product1(l: Lst[Int]): Int = Lst.foldLeft(l, 1)(_ * _)

product1(Lst(1,2,3,4))

Exercise 5: Implement function map , which changing the internal type of a list but preserves its structure.

Hint: You can use the foldLeft don't reinvent the wheel



In [ ]:

    
sealed trait Lst[+A]
case object Nil extends Lst[Nothing]
case class Cons[+A](head: A, tail: Lst[A]) extends Lst[A]

object Lst {

    def apply[A](ss: A*): Lst[A] =      
      if(ss.isEmpty) Nil
      else Cons(ss.head, apply(ss.tail: _*))
      
    def head[A](l: Lst[A]): A = l match {
       case Nil => sys.error("Invoking head on empty list.")
       case Cons(a,_) => a
    }
    
    // Collapses the list to one value using a initial element and a binary operation. 
    // This is done from rigth to left (from the last element to the first)
    def foldRight[A,B](l: Lst[A], z: B)(f: (A,B) => B): B = l match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs,z)(f))
    }
    
    // This is the tail recursive version of the operation above ( it is not always the same why?)
    // Collapses the list to one value using a initial element and a binary operation. 
    // This is done from rigth to left (from the last element to the first)
    @annotation.tailrec
    def foldLeft[A,B](l: Lst[A], z: B)(f: (B, A) => B): B = l match {
      case Nil => z
      case Cons(h,t) => foldLeft(t, f(z,h))(f)
    }
    
    def map[A,B](l: Lst[A], f: A => B): Lst[B] = ???
}
val list = Lst(1,2,3)
Lst.map(list, (i: Int) => i.toString)
Lst.map(list, (i: Int) => i + 1)

Conclusion

Data types are the way of describing how programs work in functional languages.
Side effects are described via data types too like Option and List.
Data types in scala are forming an algebra of types and often are called ADTs.
Parametric polymorphic functions are the means of abstracting and they provide general behaviours for our types (descriptions)
Do not reinvent the wheel mentally and programmatically, all the above constructs (and much more) are available in existing libraries.
Read, Read , Read and experiment. The path to ascension is closer than you think...

Resources

Functional programming in scala

Fotios Paschos, @fpaschos Oct, 2017